Ethernet was first developed to interconnect computers within a relatively localized area (i.e., a local area network (LAN)). As the popularity of Ethernet increased, Ethernet protocols were extended to permit the use of Ethernet into metropolitan area networks (MANs) and service provider networks. For example, in the Institute for Electrical and Electronics Engineers (IEEE) 802.1ad Standard protocol, a four byte tag was added to the Ethernet frame (the term “frame” is also referred to herein as a “packet”) and routing of the frame in the service provider domain is based on this additional tag and the destination media access control (MAC) address in the frame. Also, the IEEE 802.1ah Standard defines an Ethernet frame encapsulation that provides other tags so that routing in the service provider domain need not be based on the MAC address in the Ethernet frame. In this way, the customer and service provider domains can be separated. The IEEE 802.1ah Standard is sometimes referred to as “MAC-in-MAC” or M-in-M.
Network devices, such as bridges and routers, sometimes are implemented using a pipelined architecture. For example, a pipeline in a network device may process packets received by the device and then forward the packets to appropriate egress ports of the device. Because of their pipelined architecture, such network devices may be very efficient. Pipelined network devices that can accommodate hierarchical header structures, such as in are desirable.